﻿\newpage
\section{Предварительные сведения}
\label{section:theory}

{\it Алфавит} $\Sigma$~--- это произвольное непустое конечное множество, его элементы
называются {\it символами} или {\it буквами}. {\it Слово} $u$ над алфавитом $\Sigma$~--- конечная
цепочка символов из $\Sigma$ (возможна, пустая), количество символов в цепочке
называется {\it длиной} слова и обозначается как $|u|$.
Через $\Sigma^n$ обозначают множество всех слов длины
$n$ над алфавитом $\Sigma$, а через $\Sigma^{*}$~--- множество всех слов над
алфавитом $\Sigma$. Если $u = u_1 \ldots u_n = u[1..n] = u[1]u[2] \ldots u[n]$~--- слово, то цепочка символов
$v = u[i..j]$ ($1 \leq i \leq j \leq n$) называется {\it подсловом} $u$.
Говорят, что $v$ {\it встречается} в $u$ начиная с $i$-й позиции. Если $i=1$, то
$v$ является {\it префиксом} $u$, если $j=n$, то $v$ является {\it суффиксом} $u$.
Положительное целое число $p$ называется {\it периодом} $u$, если
$u[i] = u[i{+}p]$ для всех $1 \leq i \leq |u|-p$. {\it Частотный вектор}
$\vec p(u)$ слова $u$ имеет размерность $|\Sigma|$ и для каждого символа $c\in\Sigma$
содержит в $[\vec p(u)]_c$ количество вхождений $c$ в слово $u$.

\textit{Язык} над алфавитом $\Sigma$~--- произвольное подмножество
$L\subseteq\Sigma^{*}$. Язык называется \textit{факториальным}, если он
замкнут относительно взятия подслов. Все языки, которые мы рассматриваем в этой работе,
являются факториальными. Слово $w$ называется
\textit{запрещённым} в языке $L$, если оно не является подсловом никакого слова
из $L$. \textit{Антисловарь} языка $L$~--- это множество $M\subseteq\Sigma^*$,
состоящее из всех минимальных (относительно взятия подслов) запрещённых в
$L$ слов. Факториальный язык $L$ и его антисловарь $M$ удовлетворяют равенствам
$L=\Sigma^*-\Sigma^*\!M\Sigma^*$ и $M=\Sigma L\cap L\Sigma\cap(\Sigma^*{-}L)$.
Таким образом, каждый антисловарь задаёт единственный факториальный язык.

\textit{Экспонента} слова~--- это отношение длины слова к его
минимальному периоду. Данная работа посвящена языкам с ограничением на
экспоненту. Для произвольного $\beta > 1$ язык над алфавитом $\Sigma$ называется
\textit{$\beta$-свободным}
(\textit{$\beta^{+}$-свободным}), если он состоит из всех слов из $\Sigma^*$, экспоненты
всех подслов которых меньше $\beta$ (соответственно, не больше $\beta$).

\textit{Комбинаторная сложность} языка $L\subseteq\Sigma^*$~--- это
функция $C_L(n)=|L\cap\Sigma^n|$, то есть, количество слов длины $n$,
принадлежащих $L$. \textit{Индекс роста} $L$ определяется как
$\alpha(L)=\limsup\limits_{n\to\infty}(C_L(n))^{1/n}$. Например, если
$\alpha(L)=0$, то $L$ конечен, а если $\alpha(L)>1$, то $C_L(n)$ растёт экспоненциально.

Множество $M_k\subseteq\Sigma^*$ называется \textit{k-приближением} антисловаря
$M$, если оно состоит из всех слов из $M$ длины не более $k$. Пусть
$L_k$~--- язык, заданный конечным антисловарём $M_k$. Тогда $L_k$~--- регулярный,
\hbox{$M_1\subseteq \ldots\subseteq M_k\subseteq\ldots\subseteq M$} и
\hbox{$L\subseteq\ldots\subseteq L_k\subseteq\ldots\subseteq L_1$}.
Индекс роста $L_k$ является верхней оценкой индекса роста
$L$, причём $\lim\limits_{k\to\infty}\alpha(L_k) = \alpha(L)$.

Если любая перестановка множества $\Sigma$ сохраняет $L$,
то $L$ называется \textit{симметричным}.
Если одно слово можно получить из другого, применив перестановку букв алфавита,
то такие слова называются \textit{эквивалентными}. $\beta$-свободные языки
являются симметричными, и в приведённых в работе алгоритмах при построении
антисловарей этих языков в них будут заноситься только слова,
лексикографически меньшие всех своих эквивалентов. Согласно
\cite{Shur-Algo}, индекс роста языка, заданного таким сокращённым
<<антисловарём представителей>>, будет совпадать с индексом
роста языка, заданного исходным антисловарём. Это позволит нам сократить и
время работы программы, и объём используемой памяти примерно в $|\Sigma|!$ раз,
что особенно важно для изучения языков над большими алфавитами.

Когда конечное приближение антисловаря языка построено, по этому
приближению строится детерминированный конечный автомат, распознающий
соответствующий язык. Алгоритм построения такого автомата приводится
в \cite{Aho}, а в \cite{Shur-Algo} описана модификация этого алгоритма,
если вместо полного антисловаря используется антисловарь
лексикографически минимальных представителей.

Рассмотрим способ вычисления индекса роста языка по его распознающему автомату.
\textit{Индексом} ориентированного графа называют
максимальное собственное значение его матрицы смежности (\textit{корень Фробениуса}).
Все распознающие автоматы, которые мы строим по антисловарям,
являются достижимыми и кодостижимыми (любое состояние достижимо из стартового, из любого
состояния достижимо терминальное), и для них верно следующее утверждение:
индексы роста языков, распознаваемых автоматами, совпадают с индексами
орграфов этих автоматов. Таким образом, индекс роста языка, заданного конечным антисловарём,
равен максимальному собственному значению матрицы смежности распознающего автомата.
Это собственное значение можно вычислить приближённо, с любой наперёд заданной точностью.
Для вычисления мы используем быстрый и устойчивый к ошибкам округления
итеративный алгоритм, предложенный в~\cite{Shur-Algo}.
